The present invention relates generally to improved means and methods for controlling the operation of digital computers. More particularly, the present invention is directed to improved means and methods for controlling the sequencing and branching of microinstructions in a microprogrammed digital computer.
A particular architectural concept that has allowed for more flexibility in computer design and also in computer programming has been the concept of microinstructions. Initially, a microinstruction was thought of as merely a set of control bits employed within a macroinstruction format. Such control bits were employed to provide a corrective measure during the execution of a multiplying instruction or shift instruction and the like. Gradually, as the microprogramming concept enlarged, the macroinstruction specified the particular routine to be performed, such as the addition of two operands. The execution of the macroinstruction was then accomplished through a sequence of executions of microinstructions, each of which specified the particular gates to be set thereby. Since a plurality of macroinstructions could be implemented by a finite set of microinstructions, it was then apparent that these same microinstructions could be stored in a separate storage to be addressed in a particular sequence upon the execution of different macroinstructions. It was further recognized that various sequences of microinstructions could be formulated to carry out the particular operations and separately stored in any memory. Thus, a great variety of sequences of microinstructions could be created to carry out a great variety of routines.
The concept of microinstructions or microprograms, then, became one of providing sub-instructional sets which were masked or hidden from the programmer, thus, simplifying the writing of particular programs by minimizing the number of individual specific steps that had to be called for by the programmer. Furthermore, the concept of microprogramming allows the computer designer to design a more inexpensive computer system that could provide a great variety of routines to the computer user without the requirement of individual functions being implemented in hard-wired circuitry.
Microprogramming may thus be broadly viewed as a technique for designing and implementing the control function of a digital computer system as sequences of control signals that are organized on a word basis and stored in a fixed or dynamically changeable control memory. Detailed examples of some known approaches to the design of microprogrammed digital computers can be found in the book by S. S. Husson, "Microprogramming: Principles and Practices", Prentice-Hall, Inc. (1970), the contents of which are to be regarded as incorporated herein by this reference.
As will be apparent from the referenced Husson book, a prior art microprogram control memory may typically comprise a selectively addressable control memory having microinstruction control words stored at selectable addressable locations thereof. Normally, microinstruction control words are accessed sequentially from the control memory. In order to provide for branching, each control word may typically include, in addition to the microinstruction bits, special next address bits and test select bits which are applied to branching logic along with system condition signals to determine the address of the next microinstruction.
As the computer art progressed, a need arose for greater numbers and types of stored microinstruction control words to be available from the microinstruction memory which led to the provision of Read/Write microinstruction memories in which selected microinstructions could be provided from the processor main memory under program control so as to give the programmer the ability to modify the microinstruction control words in the microinstruction memory. Examples of such Read/Write microinstruction memories will be found in U.S. Pat. Nos. 3,478,322; 3,792,441 and 3,739,352.
One result of the provision of Read/Write microinstruction memories has been to permit greater control and flexibility over the particular microinstruction sequencing to be provided by a data processor as it performs its various programs. However, it has been found difficult to provide for optimization of microinstruction sequencing because of the wide variety of microinstruction flow paths which may occur in executing a program, for example, because of the many possible branching (i.e. conditional sequencing) options which are typically provided in the microinstruction flow path, each branch point normally requiring a longer time to determine the proper branch as compared to the time required when an unconditional sequence situation is present. Thus, although a data processor may provide a relatively fast performable single microinstruction cycle, the performance of a data processing operation may nevertheless not be optimum because of the particular microinstruction flow path which the data processor is caused to follow in performing the operation and the time required to make the various branching decisions. The difficulties in optimizing a data processing operation are further complicated by the fact that the provision of a particular microprogram flow path in order to optimize one type of operation may deleteriously affect the performance of other operations.